{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31-1 Binary gcd algorithm\n",
    "\n",
    "> Most computers can perform the operations of subtraction, testing the parity (odd or even) of a binary integer, and halving more quickly than computing remainders. This problem investigates the __*binary gcd algorithm*__, which avoids the remainder computations used in Euclid's algorithm.\n",
    "\n",
    "> __*a*__. Prove that if $a$ and $b$ are both even, then $\\text{gcd}(a, b) = 2 \\cdot \\text{gcd}(a/2, b/2)$.\n",
    "\n",
    "> __*b*__. Prove that if $a$ is odd and $b$ is even, then $\\text{gcd}(a, b) = \\text{gcd}(a, b/2)$.\n",
    "\n",
    "> __*c*__. Prove that if $a$ and $b$ are both odd, then $\\text{gcd}(a, b) = \\text{gcd}((a - b) / 2, b)$.\n",
    "\n",
    "> __*d*__. Design an efficient binary gcd algorithm for input integers $a$ and $b$, where $a \\ge b$, that runs in $O(\\lg a)$ time. Assume that each subtraction, parity test, and halving takes unit time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_gcd(a, b):\n",
    "    if a < b:\n",
    "        return binary_gcd(b, a)\n",
    "    if b == 0:\n",
    "        return a\n",
    "    if (a & 1 == 1) and (b & 1 == 1):\n",
    "        return binary_gcd((a - b) >> 1, b)\n",
    "    if (a & 1 == 0) and (b & 1 == 0):\n",
    "        return binary_gcd(a >> 1, b >> 1) << 1\n",
    "    if a & 1 == 1:\n",
    "        return binary_gcd(a, b >> 1)\n",
    "    return binary_gcd(a >> 1, b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31-2 Analysis of bit operations in Euclid's algorithm\n",
    "\n",
    "> __*a*__. Consider the ordinary \"paper and pencil\" algorithm for long division: dividing $a$ by $b$, which yields a quotient $q$ and remainder $r$. Show that this method requires $O((1 + \\lg q) \\lg b)$ bit operations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Number of comparisons and subtractions: $\\lceil \\lg a \\rceil - \\lceil \\lg b \\rceil + 1 = \\lceil \\lg q \\rceil$.\n",
    "\n",
    "Length of subtraction: $\\lceil \\lg b \\rceil$.\n",
    "\n",
    "Total: $O((1 + \\lg q) \\lg b)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*b*__. Define $\\mu(a, b) = (1 + \\lg a)(1 + \\lg b)$. Show that the number of bit operations performed by EUCLID in reducing the problem of computing $\\text{gcd}(a, b)$ to that of computing $\\text{gcd}(b, a~\\text{mod}~b)$ is at most $c(\\mu(a, b) - \\mu(b, a~\\text{mod}~b))$ for some sufficiently large constant $c > 0$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{array}{rlll}\n",
    "& \\mu(a, b) - \\mu(b, a~\\text{mod}~b) \\\\\n",
    "=& \\mu(a, b) - \\mu(b, r) \\\\\n",
    "=& (1 + \\lg a)(1 + \\lg b) - (1 + \\lg b)(1 + \\lg r) \\\\\n",
    "=& (1 + \\lg b)(\\lg a - \\lg r) & (\\lg r \\le \\lg b)\\\\\n",
    "\\ge& (1 + \\lg b)(\\lg a - \\lg b) \\\\\n",
    "=& (1 + \\lg b) (\\lg q + 1) \\\\\n",
    "\\ge& (1 + \\lg q) \\lg b\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*c*__. Show that EUCLID$(a, b)$ requires $O(\\mu(a, b))$ bit operations in general and $O(\\beta^2)$ bit operations when applied to two $\\beta$-bit inputs."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\mu(a, b) = (1 + \\lg a)(1 + \\lg b) \\approx \\beta^2$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31-3 Three algorithms for Fibonacci numbers\n",
    "\n",
    "> This problem compares the efficiency of three methods for computing the $n$th Fibonacci number $F_n$, given $n$. Assume that the cost of adding, subtracting, or multiplying two numbers is $O(1)$, independent of the size of the numbers.\n",
    "\n",
    "> __*a*__. Show that the running time of the straightforward recursive method for computing $F_n$ based on recurrence (3.22) is exponential in $n$. (See, for example, the FIB procedure on page 775.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$T(n) = T(n - 1) + T(n - 2) + \\Theta(1) = \\Theta(2^n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*b*__. Show how to compute $F_n$ in $O(n)$ time using memoization."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib(n):\n",
    "    fibs = [0, 1] + [-1] * (n - 1)\n",
    "\n",
    "    def fib_sub(n):\n",
    "        if fibs[n] == -1:\n",
    "            fibs[n] = fib_sub(n - 1) + fib_sub(n - 2)\n",
    "        return fibs[n]\n",
    "    return fib_sub(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*c*__. Show how to compute $F_n$ in $O(\\lg n)$ time using only integer addition and multiplication.\n",
    "(Hint: Consider the matrix\n",
    "\n",
    "> $\\displaystyle \\left (\n",
    "\\begin{matrix}\n",
    "0 & 1 \\\\\n",
    "1 & 1\n",
    "\\end{matrix}\n",
    "\\right )\n",
    "$\n",
    "\n",
    "> and its powers.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Matrix:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "\n",
    "    def __mul__(self, x):\n",
    "        a = self.data\n",
    "        b = x.data\n",
    "        c = [[0, 0], [0, 0]]\n",
    "        for i in xrange(2):\n",
    "            for j in xrange(2):\n",
    "                for k in xrange(2):\n",
    "                    c[i][j] += a[i][k] * b[k][j]\n",
    "        return Matrix(c)\n",
    "\n",
    "\n",
    "def fib(n):\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    if n == 1:\n",
    "        return 1\n",
    "    m = Matrix([[1, 1], [1, 0]])\n",
    "    r = Matrix([[1, 0], [0, 1]])\n",
    "    i = 0\n",
    "    n -= 1\n",
    "    while (1 << i) <= n:\n",
    "        if (n & (1 << i)) > 0:\n",
    "            r *= m\n",
    "        m *= m\n",
    "        i += 1\n",
    "    return r.data[0][0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*d*__. Assume now that adding two $\\beta$-bit numbers takes $\\Theta(\\beta)$ time and that multiplying two $\\beta$-bit numbers takes $\\Theta(\\beta^2)$ time. What is the running time of these three methods under this more reasonable cost measure for the elementary arithmetic operations?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. $\\Theta(2^{2^\\beta})$.\n",
    "2. $\\Theta(2^\\beta)$.\n",
    "3. $T(n) = T(n/2) + \\Theta(\\beta^2) = \\Theta(\\beta^3)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31-4 Quadratic residues\n",
    "\n",
    "> Let $p$ be an odd prime. A number $a \\in Z_p^*$ is a __*quadratic residue*__ if the equation $x^2 = a ~(\\text{mod}~p)$ has a solution for the unknown $x$.\n",
    "\n",
    "> __*a*__. Show that there are exactly $(p - 1) / 2$ quadratic residues, modulo $p$.\n",
    "\n",
    "\n",
    "> __*b*__. If $p$ is prime, we define the __*Legendre symbol*__ $(\\frac{a}{p})$, for $a \\in \\mathbb{Z}_p^*$, to be $1$ if $a$ is a quadratic residue modulo $p$ and $-1$ otherwise. Prove that if $a \\in \\mathbb{Z}_p^*$, then\n",
    "\n",
    "> $\\displaystyle \\left ( \\frac{a}{p} \\right ) \\equiv a^{(p - 1) / 2} ~(\\text{mod}~ p)$.\n",
    "\n",
    "> Give an efficient algorithm that determines whether a given number $a$ is a quadratic residue modulo $p$. Analyze the efficiency of your algorithm.\n",
    "\n",
    "> __*c*__. Prove that if $p$ is a prime of the form $4k + 3$ and $a$ is a quadratic residue in $\\mathbb{Z}_b^*$, then $a^{k+1} ~\\text{mod}~ p$ is a square root of $a$, modulo $p$. How much time is required to find the square root of a quadratic residue $a$ modulo $p$?\n",
    "\n",
    "> __*d*__. Describe an efficient randomized algorithm for finding a nonquadratic residue, modulo an arbitrary prime $p$, that is, a member of $\\mathbb{Z}_p^*$ that is not a quadratic residue. How many arithmetic operations does your algorithm require on average?"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
